#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    using LL = long long;
    int lower_bound(const vector<int>& nums, int target)
    {
        int left = 0, right = nums.size() - 1;
        while (left <= right)
        {
            int mid = (right - left) / 2 + left;
            if (nums[mid] < target)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return left;
    }
    long long countFairPairs(vector<int>& nums, int lower, int upper) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        LL res = 0;
        for (int i = 0; i < n; i++)
        {
            LL change = (lower_bound(nums, upper - nums[i] + 1) - max(i + 1, lower_bound(nums, lower - nums[i])));
            res = res + max(change, (LL)0);
        }
        return res;
    }
};